package com.datastructure.test.differentbinarysearchtree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DifferentBinarySearchTree {

    public static void main(String[] args) {

    }

    public ArrayList<TreeNode> BSTgenerate (int n) {
        // write code here
        return dfs(1,n);
    }
    public ArrayList<TreeNode> dfs(int l, int r){
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        if(l>r){
            res.add(null);
            return res;
        }
        for(int i = l;i<=r;i++){
            ArrayList<TreeNode> lc = dfs(l,i-1);
            ArrayList<TreeNode> rc = dfs(i+1,r);
            for(TreeNode lNode:lc){
                for(TreeNode rNode:rc){
                    TreeNode cur = new TreeNode(i);
                    cur.left = lNode;
                    cur.right = rNode;
                    res.add(cur);

                }
            }
        }
        return res;
    }

    public boolean isValidBST (TreeNode root) {
        // write code here
        if (root==null){
            return true;
        }
        ArrayList<Integer>a=new ArrayList<>();
        inOrder(a,root);
        for (int i=0;i<a.size()-1;i++){
            if (a.get(i)>a.get(i+1)){
                return false;
            }
        }
        return true;
    }

    private void inOrder(List<Integer> list, TreeNode root) {
        if (root==null){
            return;
        }
        inOrder(list,root.left);
        list.add(root.val);
        inOrder(list,root.right);
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }
